/*
 * funcoes.c
 *
 *  Created on: 08/05/2011
 *      Author: sheila
 */

#include <stdio.h>
#include <stdlib.h>
#include "funcoes.h"


/*no *busca(Tipo x,no *raiz,int *cont){

    while (raiz!=NULL){
        if(raiz->chave<x) raiz=raiz->dir;

        else{ if(raiz->chave>x)
                    raiz=raiz->esq;

              else if(raiz->chave==x){
                    *cont++;
                    if(raiz->esq==NULL)
                            raiz=raiz->dir;

                    else
                            raiz=raiz->esq;

                  }  }
    }
    return raiz;

    }*/

void BuscaInsere(Tipo x, no **p) {

    if (*p==NULL) {  /* se o elemento nao foi encontrado, insere */
        *p = (no *)malloc(sizeof(no));
        (*p)->chave = x;
        (*p)->esq = NULL;
        (*p)->dir = NULL;
  /*  	printf("Digite o numero de elementos da sub arvore \n");
    	scanf("%d",&((*p)->n_elem));*/
    }
    else if (x<(*p)->chave) BuscaInsere(x,&((*p)->esq));
    else if (x>(*p)->chave) BuscaInsere(x,&((*p)->dir));
}


void rot_dir(no **p){
	no *aux;
	aux=(*p)->esq;
	(*p)->esq=aux->dir;
	aux->dir=*p;
	*p=aux;
}


void rot_esq(no **p){
	no*aux;
	aux=(*p)->dir;
	(*p)->dir=aux->esq;
	aux->esq=*p;
	*p=aux;
}


void insere_topo(int x, no **p){
	/*se a arvore esta vazia e facil inserir no topo*/
	if(*p==NULL){
		*p=(no *) malloc (sizeof(no));
		(*p)->chave=x;
		/*caso houvesse mais dados, copie-os aqui*/
		(*p)->dir=(*p)->esq=NULL;
	}
	else{
		if(x<(*p)->chave){
			insere_topo(x,&(*p)->esq);
			rot_dir(p);
		}
		else if(x>(*p)->chave){
			insere_topo(x,&(*p)->dir);
			rot_esq(p);
		}
	}
}


no *selecao(int k,no *raiz){
	int t;

/*	Pode ser que o k-esimo elemento nao exista*/
	if(raiz->n_elem<k) return NULL;
	t=(raiz->esq==NULL) ? 0: raiz->esq->n_elem;
	if(t+1>k) return selecao(k,raiz->esq);
	if(t+1<k) return selecao(k-t-1,raiz->dir);
	return raiz;
}


void sobe_menor(no **p){
	if((*p)->esq !=NULL){
		sobe_menor(&(*p)->esq);
		rot_dir(p);
	}
}

no *une_dir_esq(no* e,no **d){
	/*se a sub-arvore a direita eh vazia, retorna a outra*/
	if(*d==NULL) return e;
	sobe_menor(d);
	(*d)->esq=e;
	return *d;
}


void remove_no(int x,no **p){
	no* aux;
	 /*verifica se o item esta na arvore*/
	if(*p==NULL) return;
	if(x< (*p)->chave) remove_no(x, &(*p)->esq);
	if (x> (*p)->chave) remove_no(x,&(*p)->dir);
	if (x==(*p)->chave){
		aux=*p;
		*p=une_dir_esq((*p)->esq,&(*p)->dir);
		free(aux);
	}
}


void imprime(no *raiz, int nivel){
	int i;
	if(raiz==NULL){
		return;
	}
	imprime(raiz->dir,nivel+1);

	for(i=0;i<nivel;i++) printf("        ");
	printf("%6d\n",raiz->chave);

	imprime(raiz->esq, nivel+1);
}
/*Tentei fazer um algoritmo que inserisse em ordem os elementos, soh dando n, ele esta pela metade*/

void funcao(int raizint,int *aux,no **p, int i){

	int raiz1;
	int raiz2;

	BuscaInsere(raizint,p);




		raiz1=raizint-*aux;
		printf("raiz1 %d \n", raiz1);
		raiz2=raizint+*aux;
		printf("raiz2 %d \n", raiz2);

		/*cálculo do novo auxiliar*/
		if(i==1)	{	*aux=(raizint-*aux)/2;
		}
		printf("aux %d \n",*aux);

	if(*aux>=1){
		printf("entrou no if \n");  /*nao ta atualizando o aux*/
		funcao(raiz1,aux,p,1);
		funcao(raiz2,aux,p,0);


	}
	else if(*aux==0){
			BuscaInsere(raiz1,p);
			BuscaInsere(raiz2,p);
	}
}

void lista(no **p,no **lixo){

	BuscaInsere((*p)->chave,lixo);
	remove_no((*p)->chave,p);

}
